{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Width Ramp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxWidthRamp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大宽度坡"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组&nbsp;<code>A</code>，<em>坡</em>是元组&nbsp;<code>(i, j)</code>，其中&nbsp;&nbsp;<code>i &lt; j</code>&nbsp;且&nbsp;<code>A[i] &lt;= A[j]</code>。这样的坡的宽度为&nbsp;<code>j - i</code>。</p>\n",
    "\n",
    "<p>找出&nbsp;<code>A</code>&nbsp;中的坡的最大宽度，如果不存在，返回 0 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[6,0,8,2,1,5]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[9,8,1,0,1,9,4,0,4,1]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>\n",
    "最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>2 &lt;= A.length &lt;= 50000</code></li>\n",
    "\t<li><code>0 &lt;= A[i] &lt;= 50000</code></li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-width-ramp](https://leetcode.cn/problems/maximum-width-ramp/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-width-ramp](https://leetcode.cn/problems/maximum-width-ramp/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,0,8,2,1,5]', '[9,8,1,0,1,9,4,0,4,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        s = []\n",
    "        for i in range(len(nums)):\n",
    "            if not s or nums[i] < nums[s[-1]]:\n",
    "                s.append(i)\n",
    "        res = 0\n",
    "        for i in range(len(nums))[::-1]:\n",
    "            while s and nums[s[-1]] <= nums[i]:\n",
    "                res = max(res, i-s[-1])\n",
    "                s.pop()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dandiao_list = []\n",
    "        dandiao_list.append(0)\n",
    "        #dandiao_dict = {}\n",
    "        max_depth = 0 \n",
    "        for i in range(1,len(A)):\n",
    "            if A[i] < A[dandiao_list[-1]]:\n",
    "                print(i)\n",
    "                dandiao_list.append(i)\n",
    "            for j in reversed(range(len(dandiao_list))):\n",
    "                if A[i] >= A[dandiao_list[j]]:\n",
    "                    max_depth = max(max_depth, i-dandiao_list[j])\n",
    "                else:\n",
    "                    break\n",
    "        return max_depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def binarySearch(target, hi):\n",
    "            lo = 0\n",
    "            while lo < hi:\n",
    "                mi = (lo + hi) // 2\n",
    "                if save[mi] > target:\n",
    "                    lo = mi + 1\n",
    "                else:\n",
    "                    hi = mi\n",
    "            return hi if save[hi] <= target else n\n",
    "                \n",
    "        n = len(A)\n",
    "        save, ans = [float(\"inf\")] * n, 0\n",
    "        for i, a in enumerate(A):\n",
    "            ans = max(ans, i - binarySearch(a, i - 1))\n",
    "            save[i] = min(save[i - 1], a)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        s = []\n",
    "        res = 0\n",
    "        for i, a in enumerate(A):\n",
    "            if not s or A[s[-1]] > a:\n",
    "                s.append(i)\n",
    "        for j in range(len(A))[::-1]:\n",
    "            while s and A[s[-1]] <= A[j]:\n",
    "                res = max(res, j - s.pop())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a = A\n",
    "        n = len(a)\n",
    "        \n",
    "        ans = 0\n",
    "        v = [a[0]]\n",
    "        m = [0]\n",
    "        for i in range(1, n):\n",
    "            if a[i] < v[-1]:\n",
    "                v.append(a[i])\n",
    "                m.append(i)\n",
    "            elif a[i] >= v[0]:\n",
    "                ans = max(ans, i)\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(v) - 1\n",
    "                while l < r - 1: # v[r] <= a[i] < v[l]\n",
    "                    x = (l + r) // 2\n",
    "                    if v[x] <= a[i]:\n",
    "                        r = x\n",
    "                    else:\n",
    "                        l = x\n",
    "                ans = max(ans, i - m[r])\n",
    "        return ans\n",
    "                    \n",
    "                    \n",
    "                    \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, A: List[int]) -> int:\n",
    "        re = 0\n",
    "        stack = []\n",
    "\n",
    "        for i in range(len(A)):\n",
    "            if len(stack) == 0 or A[stack[-1]] > A[i]:  # 防止下标越界，不用A[i]>A[i+1}\n",
    "                stack.append(i)  # stack中存放下标 ，按值升序\n",
    "\n",
    "        for j in range(len(A) - 1, re - 1, -1):  # 最大堆的左端肯定在单调栈内\n",
    "            while stack and A[stack[-1]] <= A[j]:\n",
    "                k = j - stack.pop()  # 对于栈顶元素来说不可能有更大值， 因此pop出\n",
    "                re = max(re, k)  #找到每个单调递增堆中元素的最大宽度坡，max即为整个数组最终结果\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, A: List[int]) -> int:\n",
    "        ans = 0\n",
    "        stack = [0] \n",
    "        for i in range(1,len(A)):\n",
    "            if A[stack[-1]] > A[i]:\n",
    "                stack.append(i)\n",
    "        j = len(A)-1\n",
    "       \n",
    "        while j > ans:\n",
    "            while stack and A[stack[-1]] <= A[j]:\n",
    "                ans = max(ans,j - stack[-1])\n",
    "                stack.pop()\n",
    "            j -= 1\n",
    "       \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, A: List[int]) -> int:\n",
    "        val = list()\n",
    "        rank = list()\n",
    "        for r, v in enumerate(A):\n",
    "            if not val or val[-1] > v:\n",
    "                val.append(v)\n",
    "                rank.append(r)\n",
    "        val.reverse()\n",
    "        rank.reverse()\n",
    "        width = 0\n",
    "        for r, v in enumerate(A):\n",
    "           i = bisect.bisect_right(val,v)\n",
    "           if i > 0 and rank[i - 1] < r:\n",
    "               width = max(width, r - rank[i - 1])\n",
    "        return width"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, A: List[int]) -> int:\n",
    "        # 寻找x左边第一个小于等于x的数\n",
    "        res = 0\n",
    "        s = [0]\n",
    "        for i in range(1, len(A)):\n",
    "            if A[s[-1]] >= A[i]:\n",
    "                s.append(i)\n",
    "        for index in range(len(A)-1, -1, -1):\n",
    "            while len(s) > 0 and A[s[-1]] <= A[index]:\n",
    "                i = s.pop()\n",
    "                res = max(index-i, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxWidthRamp(self, A):\n",
    "        ans = 0\n",
    "        m = float('inf')\n",
    "        for i in sorted(range(len(A)), key = A.__getitem__):\n",
    "            ans = max(ans, i - m)\n",
    "            m = min(m, i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxWidthRamp(self, A):\n",
    "        ans = 0\n",
    "        m = float('inf')\n",
    "        for i in sorted(range(len(A)), key = A.__getitem__):\n",
    "            ans = max(ans, i - m)\n",
    "            m = min(m, i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, A: List[int]) -> int:\n",
    "        down_stack = []\n",
    "        ans = 0\n",
    "        for i in range(len(A)):\n",
    "            if len(down_stack) == 0 or A[i] < down_stack[-1][1]:\n",
    "                down_stack.append((i,A[i]))\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(down_stack)-1\n",
    "                while l <= r:\n",
    "                    mid = (l+r)//2\n",
    "                    if A[i] >= down_stack[mid][1]:\n",
    "                        r = mid - 1\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                ans = max(ans,i-down_stack[r+1][0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, A: List[int]) -> int:\n",
    "        N = len(A)\n",
    "        candidates = [(A[N-1],N-1)]\n",
    "        ans = 0\n",
    "        for i in range(N-2,-1,-1):\n",
    "            pos = bisect.bisect(candidates, (A[i],))\n",
    "            if pos < len(candidates):\n",
    "                ans = max(ans, candidates[pos][1] - i)\n",
    "            else:\n",
    "                candidates.append((A[i],i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        stack = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if not stack or nums[stack[-1]] >= nums[i]:\n",
    "                stack.append(i)\n",
    "\n",
    "        res = 0\n",
    "        i = n - 1\n",
    "        while i > res:\n",
    "            while stack and nums[i] >= nums[stack[-1]]: # 肯定会遇到i==stack[-1]的时候！\n",
    "                res = max(res, i-stack.pop())\n",
    "            i -= 1\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if not stack or nums[stack[-1]] > nums[i]:\n",
    "                stack.append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:\n",
    "                ans = max(ans, i - stack.pop())\n",
    "            stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, num_list: List[int]) -> int:\n",
    "        n = len(num_list)\n",
    "        max_width = 0\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if not stack or num_list[stack[-1]] > num_list[i]:\n",
    "                stack.append(i)\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and num_list[stack[-1]] <= num_list[i]:\n",
    "                pos = stack.pop()\n",
    "                max_width = max(max_width, i - pos)\n",
    "\n",
    "        return max_width\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        record=[0]\n",
    "        res=0\n",
    "        for i,x in enumerate(nums[1::],1):\n",
    "            if nums[record[-1]]>=x:\n",
    "                record.append(i)\n",
    "        for i in range(len(nums)-1,0,-1):\n",
    "            while record and nums[i]>=nums[record[-1]]:\n",
    "                res=max(res,i-record.pop())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, A: List[int]) -> int:\n",
    "        stack = []\n",
    "        n = len(A)\n",
    "        for i in range(n):\n",
    "            if not stack or A[stack[-1]] > A[i]:\n",
    "                stack.append(i)\n",
    "        res = 0\n",
    "        j = n - 1\n",
    "        while j >= res:\n",
    "            while stack and A[stack[-1]] <= A[j]:\n",
    "                res = max(res,j-stack[-1])\n",
    "                stack.pop()\n",
    "            j -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        stack = []\n",
    "        stack.append(0)\n",
    "        for i in range(1,len(nums)):\n",
    "            if not stack or nums[stack[-1]] > nums[i]:\n",
    "                stack.append(i)\n",
    "        n = len(nums) - 1\n",
    "        re = 0\n",
    "        while n > re:\n",
    "            while stack and nums[n] >= nums[stack[-1]]:\n",
    "                re = max(re,n - stack[-1])\n",
    "                stack.pop()\n",
    "            n -= 1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        stack = []\n",
    "        for i in range(len(nums)):\n",
    "            if not stack or nums[stack[-1]] > nums[i]:\n",
    "                stack.append(i)\n",
    "        res = 0\n",
    "        i = len(nums) - 1\n",
    "        while i > res:\n",
    "            while stack and nums[stack[-1]] <= nums[i]:\n",
    "                res = max(res, i - stack.pop())\n",
    "            i -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    MAXN = 50001\n",
    "\n",
    "    def maxWidthRamp(self, arr):\n",
    "        r=1\n",
    "        n=len(arr)\n",
    "\n",
    "        stack=[0]*n\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if arr[stack[r-1]]>arr[i]:\n",
    "                stack[r]=i\n",
    "                r+=1\n",
    "        ans =0\n",
    "\n",
    "        for j in range(n-1,-1,-1):\n",
    "            while r>0 and arr[stack[r-1]]<=arr[j]:\n",
    "                ans =max(ans,j-stack[r-1])\n",
    "                r-=1\n",
    "        return ans\n",
    "# 示例用法\n",
    "solution = Solution()\n",
    "arr = [6, 0, 8, 2, 1, 5]\n",
    "result = solution.maxWidthRamp(arr)\n",
    "print(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        my_stack = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if len(my_stack) == 0  or nums[my_stack[-1]] >= nums[i]:\n",
    "                # my_stack.pop(-1)\n",
    "                my_stack.append(i)\n",
    "        print(my_stack)\n",
    "        ans = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while my_stack and nums[i] >= nums[my_stack[-1]]:\n",
    "                ans = max(ans, i - my_stack[-1])\n",
    "                my_stack.pop(-1)\n",
    "            if i < ans:\n",
    "                break\n",
    "\n",
    "        return ans\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        m=float('inf')\n",
    "        for i in sorted(range(len(nums)),key=nums.__getitem__):\n",
    "            ans=max(ans,i-m)\n",
    "            m=min(m,i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxWidthRamp(self, A):\n",
    "        ans = 0\n",
    "        m = float('inf')\n",
    "        for i in sorted(range(len(A)), key = A.__getitem__):\n",
    "            ans = max(ans, i - m)\n",
    "            m = min(m, i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        m = float('inf')\n",
    "        for i in sorted(range(len(nums)), key = nums.__getitem__):\n",
    "            ans = max(ans, i - m)\n",
    "            m = min(m, i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            ret = 0 if nums[i] > nums[j] else j - i\n",
    "            return max(ret, dfs(i+1, j), dfs(i, j-1))\n",
    "        return dfs(0, len(nums)-1)\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n-1, i, -1):\n",
    "                if nums[i] <= nums[j]:\n",
    "                    dp[i][j] = max(j - i, dp[i+1][j], dp[i][j-1])\n",
    "                    ret = max(ret, dp[i][j])\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            dp[-1] = 0\n",
    "            for j in range(n-1, i, -1):\n",
    "                if nums[i] <= nums[j]:\n",
    "                    dp[i] = max(j - i, dp[i], dp[i+1])\n",
    "        return max(dp)\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        st = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if not st or nums[st[-1]] > nums[i]:\n",
    "                st.append(i)\n",
    "        ret = 0\n",
    "        idx = n - 1\n",
    "        while idx > ret:\n",
    "            while st and nums[idx] >= nums[st[-1]]:\n",
    "                ret = max(ret, idx - st.pop())\n",
    "            idx -= 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        tmp = inf \n",
    "        for i in sorted(range(len(nums)), key=nums.__getitem__):\n",
    "            ret = max(ret, i - tmp)\n",
    "            tmp = min(tmp, i)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        tmp = inf \n",
    "        for i in sorted(range(len(nums)), key=lambda x: nums[x]):\n",
    "            ret = max(ret, i - tmp)\n",
    "            tmp = min(tmp, i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        xs = [(nums[-1], n - 1)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            can = bisect.bisect_right(xs, (nums[i], ))\n",
    "            if can < len(xs):\n",
    "                ans = max(ans, xs[can][1] - i)\n",
    "            else:\n",
    "                xs.append((nums[i], i))\n",
    "        return ans                                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        # 从后往前 x递增 i递减的元素(x,i)\n",
    "        arrs = [(nums[-1], n - 1)]\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            tar_idx = bisect_left(arrs, (nums[i],))\n",
    "            if tar_idx == len(arrs):\n",
    "                arrs.append((nums[i], i))\n",
    "            else:\n",
    "                ans = max(ans, arrs[tar_idx][1] - i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        srt = sorted(list(range(n)), key = lambda x: nums[x])\n",
    "        ans[srt[n-1]] = 0\n",
    "        ma = srt[n-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if ma < srt[i]:\n",
    "                ma = srt[i]\n",
    "                ans[srt[i]] = 0\n",
    "            else:\n",
    "                ans[srt[i]] = ma - srt[i]\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        a = sorted((v, i) for i, v in enumerate(nums))\n",
    "        print(a)\n",
    "        res = 0\n",
    "        mi = a[0][1]\n",
    "        n = len(a)\n",
    "\n",
    "        for j in range(1, n):\n",
    "            print(a[j][1] - a[mi][1])\n",
    "            res = max(res, a[j][1] - mi)\n",
    "            mi = min(mi, a[j][1])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        dq = []\n",
    "        for i, v in enumerate(nums):\n",
    "            dq.append((v, i))\n",
    "\n",
    "        heapq.heapify(dq)\n",
    "        ans, i = 0, len(nums)\n",
    "        for _ in range(len(nums)):\n",
    "            _, j = heapq.heappop(dq)\n",
    "            if j > i:\n",
    "                ans = max(ans, j-i)\n",
    "            else:\n",
    "                i = j\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        s = []\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            if not s or num <= s[-1][0]:\n",
    "                s.append([num, i])\n",
    "        for i in range(n-1,-1,-1):\n",
    "            num = nums[i]\n",
    "            while s and s[-1][0] <= num:\n",
    "                res = max(res, i-s[-1][1])\n",
    "                s.pop()\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        nums=sorted([(nums[i],i) for i in range(len(nums))])\n",
    "        ans,x=0,len(nums)\n",
    "        for i in nums:x=min(x,i[1]);ans=max(ans,i[1]-x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWidthRamp(self, nums: List[int]) -> int:\n",
    "        back_store = list()\n",
    "        n = len(nums)\n",
    "        back_store.append((n-1,nums[-1]))\n",
    "        front_val = nums[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if nums[i] > front_val:\n",
    "                back_store.append((i,nums[i]))\n",
    "                front_val = nums[i]\n",
    "        front_store = list()\n",
    "        front_store.append((0,nums[0]))\n",
    "        front_val = nums[0]\n",
    "        for i in range(1,n):\n",
    "            if nums[i] < front_val:\n",
    "                front_store.append((i,nums[i]))\n",
    "                front_val = nums[i]\n",
    "        back_store.reverse()\n",
    "        back_idx = 0\n",
    "        back_len = len(back_store)\n",
    "        res = 0\n",
    "        for left in front_store:\n",
    "            while back_idx+1 < back_len and back_store[back_idx+1][1] >= left[1]:\n",
    "                back_idx += 1\n",
    "            # print(f'left = {left}, back point = {back_store[back_idx]}')\n",
    "            cur_len = back_store[back_idx][0] - left[0]\n",
    "            res = max(cur_len,res)\n",
    "        return res\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
